"""
501. 二叉搜索树中的众数
树 深度优先搜素 二叉搜素树 二叉树
简单


给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树
 

示例 1：


输入：root = [1,null,2,2]
输出：[2]
示例 2：

输入：root = [0]
输出：[0]
 

提示：

树中节点的数目在范围 [1, 104] 内
-10^5 <= Node.val <= 10^5
 

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-mode-in-binary-search-tree
"""
from typing import Optional, List
from collections import defaultdict


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def findMode(self, root: Optional[TreeNode]) -> List[int]:
        num_cnt = defaultdict(int)

        def dfs(node: Optional[TreeNode]):
            if not node:
                return
            num_cnt[node.val] += 1
            dfs(node.left)
            dfs(node.right)
        dfs(root)
        print(num_cnt)
        res = []
        max_val = - 10 ** 5 - 1
        for k, v in num_cnt.items():
            if v > max_val:
                res = [k]
                max_val = v
            elif v == max_val:
                res.append(k)
        return res


if __name__ == '__main__':
    solution = Solution()

    n = TreeNode(1, right=TreeNode(2, left=TreeNode(2)))
    result = solution.findMode(n)
    print(result)
    assert set(result) == set([2])

    n = TreeNode(1, right=TreeNode(2))
    result = solution.findMode(n)
    print(result)
    assert set(result) == set([1, 2])

    n = TreeNode(0)
    result = solution.findMode(n)
    print(result)
    assert set(result) == set([0])
